package pers.qianyu.month_202101.date_20210112;

import org.junit.*;

import java.util.*;

/**
 * 93. 复原IP地址
 * https://leetcode-cn.com/problems/restore-ip-addresses/
 *
 * @author mizzle rain
 * @date 2021-01-12 20:09
 */
public class RestoreIpAddresses {
    public List<String> restoreIpAddresses(String s) {
        ArrayList<String> res = new ArrayList<>();
        String path = "";
        backTracking(res, path, s, 0, 0);
        return res;
    }

    /**
     * 深搜
     *
     * @param res   结果集
     * @param path  路径
     * @param s     原始字符串
     * @param index 当前搜索的字符索引
     * @param k     当前已经找到几段
     */
    private void backTracking(ArrayList<String> res, String path, String s, int index, int k) {
        if (index == s.length()) {
            if (k == 4) res.add(new String(path.substring(1)));
            return;
        }
        if (k == 4) return;
        if (s.charAt(index) == '0') {
            backTracking(res, path + ".0", s, index + 1, k + 1);
        } else {
            for (int i = index + 1; i <= s.length() && (i - index <= 3); i++) {
                int t = Integer.parseInt(s.substring(index, i));
                if (t < 256) {
                    backTracking(res, path + "." + t, s, i, k + 1);
                }
            }
        }
    }

    @Test
    public void test1() {
        List<String> result = new RestoreIpAddresses().restoreIpAddresses("25525511135");
        System.out.println("result = " + result);
    }
}
